package com.zang.tree;

import java.util.*;

/**
 *
 * 在每个树行中找最大值
 *
 * @author ZVerify
 * @since 2022/10/23 15:53
 * @see <a href="https://leetcode.cn/problems/find-largest-value-in-each-tree-row/">...</a>
 **/
public class 在每个树行中找最大值 {

    public List<Integer> largestValues(TreeNode root) {

        if (root == null ) return Collections.emptyList();
        if (root.left==null && root.right==null) return Collections.singletonList(root.val);

        Queue<TreeNode> list = new LinkedList<>();

        ArrayList<Integer> arrayList = new ArrayList<>();
        list.offer(root);

        while (!list.isEmpty()) {

            int max = Integer.MIN_VALUE;
            int size = list.size();
            for (int i = 0; i< size; i++) {
                TreeNode poll = list.poll();
                max = Math.max(max, poll.val);
                if (poll.left != null) list.offer(poll.left);
                if (poll.right != null) list.offer(poll.right);
            }
            arrayList.add(max);
        }
        return arrayList;
    }
}
